package LeetCode;

import java.util.List;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}10:32
 */
public class DP02 {
    public static void main(String[] args) {
        int[] arr = {3,100,4,12,5,2};
        System.out.println(rec_subset(arr, 0, 100));
        System.out.println(dp_subset(arr, 100));
    }

    public static boolean rec_subset(int[] arr,int index,int s){
        if (s == 0){
            return true;
        }
        if (index == arr.length - 1){
            return arr[index] == s;
        }
        if (arr[index] > s){
            return rec_subset(arr,index + 1,s);
        }else {
            return rec_subset(arr,index + 1,s - arr[index]) || rec_subset(arr,index + 1,s);
        }
    }

    public static boolean dp_subset(int[] arr,int s){
        boolean[][] dp = new boolean[arr.length][s+1];

        for (int i = 0; i < dp[0].length; i++){
            dp[0][i] = false;
        }
        for (int i = 0; i < dp.length; i++){
            dp[i][0] = true;
        }
        for (int i = 1; i < dp.length; i++){
            for (int j = 1; j < dp[i].length; j++){
                if (arr[i] > j){
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = dp[i - 1][s-arr[i]] || dp[i - 1][j];
                }
            }
        }
        return dp[arr.length-1][s];
    }
}
